/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {

    /**
     * head [1,2,3,4,5]
     * start
     * end
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode start = dummy;
        ListNode end = start;
        int cnt = 0;
        while (end != null && cnt < n) {
            cnt++;
            end = end.next;
        }
        while (end.next != null) {
            start = start.next;
            end = end.next;
        }
        start.next = start.next.next;
        return dummy.next;
    }


    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(array[0]);
        ListNode pre = head;
        for (int i = 1; i < array.length; i++) {
            ListNode listNode = new ListNode(array[i]);
            pre.next = listNode;
            pre = listNode;
        }
        Solution solution = new Solution();
        ListNode listNode = solution.removeNthFromEnd(head, 5);

        System.out.println("  ");
    }

    // 本算法使用递归实现，一趟扫描完成需求开发，建议使用双指针。
}